翻訳と辞書 Words near each other ・ Pollara ・ Pollard ・ Pollard (novel) ・ Pollard (surname) ・ Pollard Banknote ・ Pollard Baptist Church ・ Pollard baronets ・ Pollard Glacier ・ Pollard Hopewell ・ Pollard Kot ・ Pollard Meadows, Edmonton ・ Pollard railway station ・ Pollard script ・ Pollard Syndrum ・ Pollard's Chicken ・ Pollard's kangaroo algorithm ・ Pollard's p − 1 algorithm ・ Pollard's rho algorithm ・ Pollard's rho algorithm for logarithms ・ Pollard, Alabama ・ Pollard, Arkansas ・ Pollard, Kansas ・ Pollard, Washington ・ Pollard-Nelson House ・ Pollarding ・ Pollards Corner, Virginia ・ Pollards Hill ・ Pollards Point ・ Pollari ・ Pollatoomary Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Pollard's kangaroo algorithm ： ウィキペディア英語版 Pollard's kangaroo algorithm In computational number theory and computational algebra, Pollard's kangaroo algorithm (aka Pollard's lambda algorithm, see Naming below) is an algorithm for solving the discrete logarithm problem. The algorithm was introduced in 1978 by the number theorist J. M. Pollard, in the same paper 〔J. Pollard, ''Monte Carlo methods for index computation mod p'', Mathematics of Computation, Volume 32, 1978〕 as his better-known ρ algorithm for solving the same problem. Although Pollard described the application of his algorithm to the discrete logarithm problem in the multiplicative group of units modulo a prime ''p'', it is in fact a generic discrete logarithm algorithm—it will work in any finite cyclic group. ==The algorithm== Suppose $G$ is a finite cyclic group of order $n$ which is generated by the element $\backslash alpha$, and we seek to find the discrete logarithm $x$ of the element $\backslash beta$ to the base $\backslash alpha$. In other words, we seek $x\; \backslash in\; Z\_n$ such that $\backslash alpha^x\; =\; \backslash beta$. The lambda algorithm allows us to search for $x$ in some subset $\backslash \backslash subset\; Z\_n$. We may search the entire range of possible logarithms by setting $a=0$ and $b=n-1$, although in this case Pollard's rho algorithm is more efficient. We proceed as follows: 1. Choose a set $S$ of integers and define a pseudorandom map $f:\; G\; \backslash rightarrow\; S$. 2. Choose an integer $N$ and compute a sequence of group elements $\backslash$ according to: * $x\_0\; =\; \backslash alpha^b\backslash ,$ * $x\_\; =\; x\_i\backslash alpha^\backslash mboxi=0,1,\backslash ldots,N-1$ 3. Compute :$d\; =\; \backslash sum\_^f(x\_i)$. Observe that: :$x\_N\; =\; x\_0\backslash alpha^d\; =\; \backslash alpha^\backslash ,\; .$ 4. Begin computing a second sequence of group elements $\backslash$ according to: * $y\_0\; =\; \backslash beta\backslash ,$ * $y\_\; =\; y\_i\backslash alpha^\backslash mboxi=0,1,\backslash ldots,N-1$ and a corresponding sequence of integers $\backslash$ according to: :$d\_n\; =\; \backslash sum\_^f(y\_i)$. Observe that: :$y\_i\; =\; y\_0\backslash alpha^\; =\; \backslash beta\backslash alpha^\backslash mboxi=0,1,\backslash ldots,N-1$ 5. Stop computing terms of $\backslash$ and $\backslash$ when either of the following conditions are met: :A) $y\_j\; =\; x\_N$ for some $j$. If the sequences $\backslash$ and $\backslash$ "collide" in this manner, then we have: ::$x\_N\; =\; y\_j\; \backslash Rightarrow\; \backslash alpha^\; =\; \backslash beta\backslash alpha^\; \backslash Rightarrow\; \backslash beta\; =\; \backslash alpha^\; \backslash pmod\; \backslash Rightarrow$ x \equiv b+d-d_j \pmod :and so we are done. :B) $d\_i\; >\; b-a+d$. If this occurs, then the algorithm has failed to find $x$. Subsequent attempts can be made by changing the choice of $S$ and/or $f$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pollard's kangaroo algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.